package aco;

import java.util.ArrayList;

// 【蚁群类】
public class Ants {

    // 【蚂蚁类】 静态内部类，可以脱离外部类单独实例化
    static class Ant {
        // for each of the m salesmen, an ant will construct a tour, so that a candidate solution constructed by
        // an ant will be represented by a list of tours, one for each salesman
        // 一个蚂蚁代表一个解，一个解中有多条路径，每条路径有一个旅行商

        ArrayList<ArrayList<Integer>> tours; // 此蚂蚁路径集合
        ArrayList<Double> tour_lengths; // 蚂蚁每条路径的长度
        boolean visited[]; // 存储城市是否被访问的数组（不包含仓库）

        // contains the beginning of service for each customer, including the depot,
        // taking into account the opening time (beginning) of the time window,
        // the service time and the distance between customers
        // 城市的开始服务时间，索引为城市编号
        double[] beginService;

        // current number of used vehicles (= number of routes/tours) for constructing a feasible solution
        // that serve all the customers' requests and satisfy the time windows and capacity constraints
        // 此解（蚂蚁）使用的车辆数
        int usedVehicles;

        // stores for each partial tour/route under construction the current time
        // taking into account the beginning time of service for the last visited customer on the tour
        // 路径末端城市的开始服务时间，即为当前时间
        ArrayList<Double> currentTime;

        // used by the insertion heuristic when checking the feasibility of an insertion
        // it stores for every customer i already assigned to a route the earliest time a delivery can be made at i
        // 规划的每条路径中，每个客户点的最早到达时间（在时间窗范围内，如果早于时间窗的开始时间，就将时间窗的开始时间作为earliestTime）
        ArrayList<ArrayList<Double>> earliestTime;

        // used by the insertion heuristic when checking the feasibility of an insertion
        // it stores for every customer i already assigned to a route the latest time a delivery can be made at i
        // 规划的每条路径中，每个客户点的最迟到达时间（在时间窗范围内，实际到达时间和时间窗结束时间取最小）
        ArrayList<ArrayList<Double>> latestTime;

        // stores for each partial tour/route under construction the current quantity of goods
        // (given by the demand of each request) transported on the route
        ArrayList<Double> currentQuantity; // 每条路径的当前载量

        double total_tour_length; // 总的路径长度
        double longest_tour_length; // 最长的路径长度
        int indexLongestTour;  // the index of the longest tour

        // cities left to be visited by an ant
        // (initially toVisit = n, which is the number of cities from the mTSP instance)
        int toVisit; // 可访问城市集合中，还未访问的城市数量

        // stores the cost of each solution according to the considered objectives (2 in this case)
        double costObjectives[]; // 存储两个优化目标值

        // it is true if a new empty tour was added in the ant solution to service the
        // remaining available unrouted/unvisited customers
        // 是否要添加新的车辆，增加新的路径
        boolean addedEmptyTour;
    }

    static Ant ants[]; // 蚁群
    static int n_ants; /* number of ants */

    /* length of nearest neighbor lists for the ants' solution construction */
    /* 表示为当前城市寻找邻近城市的数量 */
    static int nn_ants;

    // volatile关键字，它能够使变量在值发生改变时能尽快地让其他线程知道
    public volatile static Ant best_so_far_ant; // 至今为止最好的蚂蚁
    static Ant restart_best_ant; // 当前蚁群的最优蚂蚁


    static double[][] pheromone; /* 蚁群的信息素矩阵 */

    static double rho; /* 全局信息素衰变 parameter for evaporation used in global pheromne update*/
    static double local_rho;  /* 局部信息素衰变 parameter for evaporation used in local pheromone update*/
    static double alpha; /* importance of trail */
    static double beta; /* importance of heuristic evaluate */
    static double q_0; /* probability of best choice in tour construction */

    static double trail_0; /* initial pheromone level in ACS */

    // 计算 mij
    public static final double weight1 = 0.4;  //0.3   //0.4
    public static final double weight2 = 0.4;  //0.5   //0.4
    public static final double weight3 = 0.2;  //0.2   //0.2

    /* 存储城市是否被锁定的数组 */
    // 数组中不包含仓库，城市索引从0开始
    // it indicates that node at position/index i is committed if the value at position i is true;
    // the depot node is considered to be committed by default and it's not included in this array
    // 保证了变量的可见性（visibility）。被volatile关键字修饰的变量，如果值发生了变更，其他线程立马可见，避免出现脏读的现象。
    public volatile static boolean[] committedNodes;

    /**
     * TONNH(time-oriented nearest neighbour heuristic)
     * 尝试将所有订单插入到indexSalesman路径中，直到有不能插入的请求为止
     *
     * @param a             解（蚂蚁）
     * @param indexSalesman 处理路径
     * @param vrp           算例
     */
    static void choose_closest_next(Ant a, int indexSalesman, VRPTW vrp) {
        int current_city, next_city, indexTour;
        double distance, distanceDepot, arrivalTime, arrivalTimeDepot, beginService, beginServiceDepot;
        double timeDiference, deliveryUrgency, bestBeginService = 0, minValue, metricValue;
        ArrayList<Request> reqList = vrp.getRequests();
        ArrayList<Integer> idKnownRequests = vrp.getIdAvailableRequests();
        next_city = VRPTW.n; // 初始化一个不可能的值，如果到最后这个值没变化，则说明没有找到合适的匹配

        // 1.路径末端访问城市
        int lastPos = a.tours.get(indexSalesman).size() - 1;
        current_city = a.tours.get(indexSalesman).get(lastPos);
        current_city++;

        // 2.为路径末端城市匹配下一个访问城市
        minValue = Integer.MAX_VALUE;
        for (int city : idKnownRequests) {
            if (a.visited[city])
                ;  //city already visited
            else {
                distance = VRPTW.instance.distance[current_city][city + 1];
                arrivalTime = a.currentTime.get(indexSalesman) + reqList.get(current_city).getServiceTime() + distance;
                beginService = Math.max(arrivalTime, reqList.get(city + 1).getStartWindow());

                distanceDepot = VRPTW.instance.distance[city + 1][0];
                arrivalTimeDepot = beginService + reqList.get(city + 1).getServiceTime() + distanceDepot;
                beginServiceDepot = Math.max(arrivalTimeDepot, reqList.get(0).getStartWindow());
                if (VRPTW_ACS.isFeasible(vrp, a, city, beginService, beginServiceDepot, indexSalesman)) {
                    // compute the value of the "closeness" metric;
                    // this metric tries to account for both geographical and temporal closeness of customers
                    timeDiference = beginService - a.beginService[current_city] - reqList.get(current_city).getServiceTime();
                    deliveryUrgency = reqList.get(city + 1).getEndWindow() - (a.beginService[current_city] + reqList.get(current_city).getServiceTime() + distance);
                    metricValue = weight1 * distance + weight2 * timeDiference + weight3 * deliveryUrgency;
                    if (metricValue < minValue) {
                        next_city = city;
                        minValue = metricValue;
                        bestBeginService = beginService;
                    }
                }
            }
        }
        // 3.如果未能处理城市，则添加新路径用于下次调用本方法时使用
        // it means that not all the cities are covered and some customers has not yet been serviced
        // by using insertion heuristic try to insert in the current tour of the solution under construction
        // the customers not visited yet
        // when no more customer with feasible insertions can be found, start a new route/tour and add
        // one more vehicle for constructing a feasible solution
        if (next_city == VRPTW.n) {
            // 添加新路径
            // if no more unrouted customers can be feasible inserted in the solution and there are still
            // remaining unrouted customers, add a new tour
            if (a.toVisit > 0) {
                a.usedVehicles++;
                indexTour = a.usedVehicles - 1;
                a.tours.add(indexTour, new ArrayList<Integer>());
                a.tours.get(indexTour).add(-1);
                a.tour_lengths.add(indexTour, 0.0);
                a.currentQuantity.add(indexTour, 0.0);
                a.currentTime.add(indexTour, 0.0);
            }
        // 4.如果可以处理城市
        }else {
            a.tours.get(indexSalesman).add(next_city);
            a.visited[next_city] = true;
            a.toVisit--;
            a.currentTime.set(indexSalesman, bestBeginService);
            a.beginService[next_city + 1] = bestBeginService;
            a.currentQuantity.set(indexSalesman, a.currentQuantity.get(indexSalesman) + reqList.get(next_city + 1).getDemand());
        }
    }

    /**
     * 处理静态城市请求，初始化解，[time-oriented nearest neighbour heuristic]
     * generate a nearest neighbor tour and compute tour length using only the available nodes (nodes known so far)
     *
     * @return 初始解的总路径长度
     */
    static double nn_tour(VRPTW instance) {
        int salesman = 0; // 路径个数
        int step; // 路径中访问点个数
        double sum = 0, sum1 = 0, scalledValue = 0;

        // 1.清空蚂蚁信息，以 ants[0]作为初始解
        ant_empty_memory(ants[0], instance);

        // 2.蚂蚁的每条路径均从仓库出发（仓库的编号为-1）
        // place the ant on the depot city, which is the start city of each tour
        for (int i = 0; i < ants[0].usedVehicles; i++) {
            ants[0].tours.get(i).add(-1);
        }

        // 3.将所有的静态城市都处理完
        while (ants[0].toVisit > 0) {
            // 在当前现有路径不能处理完订单时，需要开辟新路径，将未处理的订单插入到新路径中，因此对新的路径操作
            salesman = ants[0].usedVehicles - 1;
            choose_closest_next(ants[0], salesman, instance);
        }

        // 4.每条路径最终回到的仓库
        for (int i = 0; i < ants[0].usedVehicles; i++) {
            step = ants[0].tours.get(i).size();
            ants[0].tours.get(i).add(step, -1); // 回到仓库
            ants[0].tour_lengths.set(i, VRPTW.compute_tour_length(ants[0].tours.get(i))); // 路径长度
            sum += ants[0].tour_lengths.get(i); // 所有路径总长
        }
        ants[0].total_tour_length = sum;

        // 5.局部搜索，进行优化
        ants[0] = VRPTW_ACS.relocateMultipleRouteIterated(ants[0], instance);
        ants[0] = VRPTW_ACS.exchangeMultipleRouteIterated(ants[0], instance);
        for (int l = 0; l < ants[0].usedVehicles; l++) {
            ants[0].tour_lengths.set(l, VRPTW.compute_tour_length(ants[0].tours.get(l))); // 路径长度
            sum1 += ants[0].tour_lengths.get(l); // 所有路径总长
        }
        ants[0].total_tour_length = sum1;

        // 6.返回并输出初始化解的结果
        // update scalingValue
        double scalingValue = Controller.getScalingValue();
        if (scalingValue != 0) {
            scalledValue = ants[0].total_tour_length / scalingValue;
        }
        System.out.println("\nInitial (nearest neighbour tour) total tour length: " + ants[0].total_tour_length + " (scalled value = " + scalledValue + "); Number of vehicles used: " + ants[0].usedVehicles);
        Ants.copy_from_to(ants[0], Ants.best_so_far_ant, instance); // 初始化全局最优蚂蚁
        ant_empty_memory(ants[0], instance);
        return sum1;
    }

    /**
     * 清空蚂蚁 a 的记录，重置蚂蚁
     * empty the ants's memory regarding visited cities
     */
    static void ant_empty_memory(Ant a, VRPTW instance) {
        int i, j;
        a.total_tour_length = 0;
        a.longest_tour_length = Integer.MAX_VALUE;
        a.indexLongestTour = 0;
        a.addedEmptyTour = false;

        a.tour_lengths.clear();
        a.currentQuantity.clear();
        a.currentTime.clear();

        for (int indexObj = 0; indexObj < 2; indexObj++) {
            a.costObjectives[indexObj] = 0;
        }

        // clear all the elements (cities) from the tours of an ant
        for (i = 0; i < a.usedVehicles; i++) {
            a.tours.get(i).clear();
        }
        a.tours.clear();

        // 初始化一条空路径
        a.usedVehicles = 1;
        for (i = 0; i < a.usedVehicles; i++) {
            a.tour_lengths.add(i, 0.0);
            a.currentQuantity.add(i, 0.0);
            a.currentTime.add(i, 0.0);
            a.tours.add(i, new ArrayList<Integer>());
        }

        if (a.earliestTime != null) {
            a.earliestTime.clear();
        }
        if (a.latestTime != null) {
            a.latestTime.clear();
        }

        for (j = 0; j < VRPTW.n; j++) {
            a.visited[j] = false;
        }
        for (j = 0; j < (VRPTW.n + 1); j++) {
            a.beginService[j] = 0;
        }

        // the another node is the depot, which is by default visited by each salesman and added in its tour
        a.toVisit = instance.getIdAvailableRequests().size();
    }

    /* 复制蚂蚁 copy solution from ant a into ant a2 */
    static void copy_from_to(Ant a1, Ant a2, VRPTW instance) {

        int i, j;
        Ants.ant_empty_memory(a2, instance);
        a2.total_tour_length = a1.total_tour_length;
        a2.toVisit = a1.toVisit;

        for (int indexObj = 0; indexObj < 2; indexObj++) {
            a2.costObjectives[indexObj] = a1.costObjectives[indexObj];
        }

        if (a2.usedVehicles < a1.usedVehicles) {
            for (int index = a2.usedVehicles; index < a1.usedVehicles; index++) {
                a2.tour_lengths.add(index, 0.0);
                a2.tours.add(index, new ArrayList<Integer>());
                a2.currentQuantity.add(index, 0.0);
                a2.currentTime.add(index, 0.0);
            }
        }

        for (i = 0; i < a1.usedVehicles; i++) {
            a2.tour_lengths.set(i, a1.tour_lengths.get(i));
            a2.currentQuantity.set(i, a1.currentQuantity.get(i));
            a2.currentTime.set(i, a1.currentTime.get(i));
            int size = a1.tours.get(i).size();
            for (j = 0; j < size; j++) {
                int elem = a1.tours.get(i).get(j);
                a2.tours.get(i).add(elem);
            }
        }
        for (i = 0; i < VRPTW.n; i++) {
            a2.visited[i] = a1.visited[i];
        }
        a2.usedVehicles = a1.usedVehicles;

        for (i = 0; i < (VRPTW.n + 1); i++) {
            a2.beginService[i] = a1.beginService[i];
        }
    }

    /* 【重置蚁群和局部最优蚂蚁】 allocate the memory for the ant colony, the best-so-far ant */
    static void allocate_ants(VRPTW instance) {
        int i, j;
        ants = new Ant[n_ants];

        // 1.将当前问题实例的所有请求城市都配置为未被锁定状态
        committedNodes = new boolean[VRPTW.n];
        for (i = 0; i < VRPTW.n; i++) {
            committedNodes[i] = false;
        }

        // 2.重置蚁群
        for (i = 0; i < n_ants; i++) {
            ants[i] = new Ant();
            ants[i].tours = new ArrayList();
            ants[i].tour_lengths = new ArrayList<Double>();
            ants[i].beginService = new double[VRPTW.n + 1];
            ants[i].currentTime = new ArrayList<Double>();
            ants[i].currentQuantity = new ArrayList<Double>();
            ants[i].usedVehicles = 1;
            ants[i].addedEmptyTour = false;
            for (j = 0; j < ants[i].usedVehicles; j++) {
                ants[i].tours.add(j, new ArrayList<Integer>());
                ants[i].tour_lengths.add(j, 0.0);
            }
            ants[i].visited = new boolean[VRPTW.n];
            // the another node is the depot, which is by default visited by each salesman and added in its tour
            ants[i].toVisit = instance.getIdAvailableRequests().size();
            ants[i].costObjectives = new double[2];
            for (int indexObj = 0; indexObj < 2; indexObj++) {
                ants[i].costObjectives[indexObj] = 0;
            }
            ants[i].earliestTime = new ArrayList(ants[i].usedVehicles);
            ants[i].latestTime = new ArrayList(ants[i].usedVehicles);
        }

        // 3.重置全局最优蚂蚁
        best_so_far_ant = new Ant();
        best_so_far_ant.tours = new ArrayList();
        best_so_far_ant.tour_lengths = new ArrayList<Double>();
        best_so_far_ant.beginService = new double[VRPTW.n + 1];
        best_so_far_ant.currentTime = new ArrayList<Double>();
        best_so_far_ant.currentQuantity = new ArrayList<Double>();
        best_so_far_ant.usedVehicles = 1;
        best_so_far_ant.addedEmptyTour = false;
        for (j = 0; j < best_so_far_ant.usedVehicles; j++) {
            best_so_far_ant.tours.add(j, new ArrayList<Integer>());
            best_so_far_ant.tour_lengths.add(j, 0.0);
        }
        best_so_far_ant.visited = new boolean[VRPTW.n];
        // the another node is the depot, which is by default visited by each salesman and added in its tour
        best_so_far_ant.toVisit = instance.getIdAvailableRequests().size();
        best_so_far_ant.longest_tour_length = Double.MAX_VALUE;

        best_so_far_ant.costObjectives = new double[2];
        for (int indexObj = 0; indexObj < 2; indexObj++) {
            best_so_far_ant.costObjectives[indexObj] = 0;
        }
        best_so_far_ant.earliestTime = new ArrayList(best_so_far_ant.usedVehicles);
        best_so_far_ant.latestTime = new ArrayList(best_so_far_ant.usedVehicles);

        // 4.重置局部最优蚂蚁
        restart_best_ant = new Ant();
        restart_best_ant.tours = new ArrayList();
        restart_best_ant.tour_lengths = new ArrayList<Double>();
        restart_best_ant.beginService = new double[VRPTW.n + 1];
        restart_best_ant.currentTime = new ArrayList<Double>();
        restart_best_ant.currentQuantity = new ArrayList<Double>();
        restart_best_ant.usedVehicles = 1;
        restart_best_ant.addedEmptyTour = false;
        for (j = 0; j < restart_best_ant.usedVehicles; j++) {
            restart_best_ant.tours.add(j, new ArrayList<Integer>());
            restart_best_ant.tour_lengths.add(j, 0.0);
        }
        restart_best_ant.visited = new boolean[VRPTW.n];
        // the another node is the depot, which is by default visited by each salesman and added in its tour
        restart_best_ant.toVisit = instance.getIdAvailableRequests().size();
        restart_best_ant.longest_tour_length = Double.MAX_VALUE;

        restart_best_ant.costObjectives = new double[2];
        for (int indexObj = 0; indexObj < 2; indexObj++) {
            restart_best_ant.costObjectives[indexObj] = 0;
        }
        restart_best_ant.earliestTime = new ArrayList(restart_best_ant.usedVehicles);
        restart_best_ant.latestTime = new ArrayList(restart_best_ant.usedVehicles);
    }

    /* Initialize pheromone trails */
    static void init_pheromone_trails(double init_trail) {
        int i, j;
        for (i = 0; i < (VRPTW.n + 1); i++) {
            for (j = 0; j <= i; j++) {
                Ants.pheromone[i][j] = init_trail;
                Ants.pheromone[j][i] = init_trail;
            }
        }
    }

    /**
     * 将上次蚁群优化线程中的最优解的信息素，初始化本次蚁群优化线程的信息素矩阵
     * 全局最优蚂蚁更新信息素
     * preserve some of the pheromone level on the edges between available nodes
     */
    static void preservePheromones(VRPTW vrp) {
        ArrayList<Integer> IdAvailableRequests = vrp.getIdAvailableRequests();
        for (int i = 0; i < (VRPTW.n + 1); i++) {
            for (int j = 0; j <= i; j++) {
                if (IdAvailableRequests.contains(i - 1) && IdAvailableRequests.contains(j - 1)
                        || ((j == 0) && IdAvailableRequests.contains(i - 1))
                        || ((i == 0) && IdAvailableRequests.contains(j - 1))) {
                    Ants.pheromone[i][j] = pheromone[i][j] * (1 - InOut.pheromonePreservation) + InOut.pheromonePreservation * trail_0;
                    Ants.pheromone[j][i] = Ants.pheromone[i][j];
                } else {
                    pheromone[i][j] = trail_0;
                    pheromone[j][i] = pheromone[i][j];
                }
            }
        }
    }

    /**
     * if rand(0, 1) < q_0 服务于[joint mechanism; neighbour_choose_and_move_to_next]
     * 执行以下代码
     */
    static int[] neighbour_choose_best_next(Ant a, VRPTW vrp) {
        int i, current_city, next_city, help_city, salesman = 0, startPos;
        double value_best = -1;  //values in total matrix are always >= 0.0
        double help;
        double distance, distanceDepot, arrivalTime, arrivalTimeDepot, beginService, beginServiceDepot;
        double timeDiference = 0, deliveryUrgency, bestBeginService = 0;
        int[] values = new int[2];
        ArrayList<Request> reqList = vrp.getRequests();
        next_city = VRPTW.n; // 初始化一个不可能的值，如果到最后这个值没变化，则说明没有找到合适的匹配
        //next_city = Integer.MAX_VALUE;

        // 1. 设定开始遍历的路径（如果上次添加了新路径，说明之前的路径不足以处理现有城市请求，所以可直接从新路径开始遍历）
        if (a.addedEmptyTour) {
            startPos = a.usedVehicles - 1;
        } else {
            startPos = 0;
        }

        // 2.尝试匹配路径indexSalesman和城市help_city
        for (int indexSalesman = startPos; indexSalesman < a.usedVehicles; indexSalesman++) {
            // 2.1 找到当前路径的末端城市
            int lastPos = a.tours.get(indexSalesman).size() - 1;
            current_city = a.tours.get(indexSalesman).get(lastPos);
            current_city++;

            // 2.2 遍历[candidate list]，遍历当前城市的临近城市集合(按照到current_city的距离,由小到大进行遍历)
            for (i = 0; i < nn_ants; i++) {
                // 2.2.1 获取城市编号 help_city
                help_city = VRPTW.instance.nn_list[current_city][i];
                // 2.2.2 如果城市help_city在可访问城市请求的集合中,且还未被访问过，则可以尝试计算help的值
                if ((vrp.getIdAvailableRequests().contains(help_city - 1)) && (!a.visited[help_city - 1])) {
                    distance = VRPTW.instance.distance[current_city][help_city];
                    arrivalTime = a.currentTime.get(indexSalesman) + reqList.get(current_city).getServiceTime() + distance;
                    beginService = Math.max(arrivalTime, reqList.get(help_city).getStartWindow());

                    distanceDepot = VRPTW.instance.distance[help_city][0];
                    arrivalTimeDepot = beginService + reqList.get(help_city).getServiceTime() + distanceDepot;
                    beginServiceDepot = Math.max(arrivalTimeDepot, reqList.get(0).getStartWindow());

                    // 2.2.3 判断将城市help_city插入到路径indexSalesman是否可行?
                    if (VRPTW_ACS.isFeasible(vrp, a, help_city - 1, beginService, beginServiceDepot, indexSalesman)) {

                        // 2.2.4 计算当前城市current_city与下一个访问城市city的紧密程度help，越大越好
                        deliveryUrgency = reqList.get(help_city).getEndWindow() - (a.beginService[current_city] + reqList.get(current_city).getServiceTime() + distance);
                        timeDiference = beginService - a.beginService[current_city] - reqList.get(current_city).getServiceTime();
                        help = 1.0 / (weight1 * distance + weight2 * timeDiference + weight3 * deliveryUrgency);
                        help = Math.pow(help, beta);
                        help = help * Math.pow(pheromone[current_city][help_city], alpha);

                        // 2.2.5 如果较前一个匹配更优
                        if (help > value_best) {
                            value_best = help;
                            next_city = help_city - 1;
                            salesman = indexSalesman;
                            bestBeginService = beginService;
                        }
                    }
                }
            }
        }

        // 3.如果有未处理城市请求，使用插入启发式方法，开辟新路径
        if (next_city == VRPTW.n) {
            // all cities in nearest neighbor list were already visited
            // 用choose_best_next(a, vrp)方法再操作一遍（在更大范围内搜索一下）,顺便生成新的路径
            values = choose_best_next(a, vrp);
            return values;
        }

        // 4.如果邻近城市集合可以匹配到路径
        else {
            a.tours.get(salesman).add(next_city);
            a.visited[next_city] = true;
            a.toVisit--;
            a.currentTime.set(salesman, bestBeginService);
            a.beginService[next_city + 1] = bestBeginService;
            double newQuantity = a.currentQuantity.get(salesman) + reqList.get(next_city + 1).getDemand();
            a.currentQuantity.set(salesman, newQuantity);
            values[0] = next_city;
            values[1] = salesman;
            return values;
        }
    }

    /**
     * 服务于[joint mechanism; neighbour_choose_and_move_to_next]
     * choose for an ant as the next city the one with maximal value of heuristic information times pheromone
     */
    static int[] choose_best_next(Ant a, VRPTW vrp) {
        int current_city, next_city, salesman = 0, indexTour, startIndex, startIndexTour = 0;
        double value_best = -1.;  /* values in total matrix are always >= 0.0 */
        double help;
        int[] values = new int[2];
        double distance, distanceDepot, arrivalTime, arrivalTimeDepot, beginService, beginServiceDepot;
        double currentTime = 0, timeDiference = 0, waitingTIme, waiting, deliveryUrgency, bestBeginService = 0;
        ArrayList<Request> reqList = vrp.getRequests();
        ArrayList<Integer> idKnownRequests = vrp.getIdAvailableRequests();
        ArrayList<Integer> lastCommitedIndexes;
        int pos;
        boolean appliedInsertion = false;

        next_city = VRPTW.n; // 初始化一个不可能的值，如果到最后这个值没变化，则说明没有找到合适的匹配

        // 1.确定开始遍历的路径
        // 判断上次操作是否添加了新的车辆路径处理当前的城市请求集合，确定开始查找的路径
        if (a.addedEmptyTour) {
            startIndex = a.usedVehicles - 1;
        } else {
            startIndex = 0;
        }

        // 2.尝试匹配每条路径和每个请求城市，找到最优的匹配方案：next_city, salesman, bestBeginService
        for (int indexSalesman = startIndex; indexSalesman < a.usedVehicles; indexSalesman++) {
            // 2.1 遍历每条路径，获取当前路径中，最后访问城市的编号，作为当前城市current_city。
            int lastPos = a.tours.get(indexSalesman).size() - 1;
            current_city = a.tours.get(indexSalesman).get(lastPos);
            current_city++;

            // 2.2 遍历可访问城市
            for (int city : idKnownRequests) {
                if (a.visited[city])
                    ; /* city already visited, do nothing */
                else {
                    // 2.2.1 计算，离开编号为current_city的城市后，开始为编号为city的城市服务的时间
                    distance = VRPTW.instance.distance[current_city][city + 1];
                    arrivalTime = a.currentTime.get(indexSalesman) + reqList.get(current_city).getServiceTime() + distance;
                    beginService = Math.max(arrivalTime, reqList.get(city + 1).getStartWindow());

                    // 2.2.2 计算，离开编号为city的城市后，开始为仓库服务的时间
                    distanceDepot = VRPTW.instance.distance[city + 1][0];
                    arrivalTimeDepot = beginService + reqList.get(city + 1).getServiceTime() + distanceDepot;
                    beginServiceDepot = Math.max(arrivalTimeDepot, reqList.get(0).getStartWindow());

                    // 2.2.3 判断将编号为city的城市，加入到蚂蚁a的，编号为indexSalesman的路径，是否可行。如果可行则计算help
                    if (VRPTW_ACS.isFeasible(vrp, a, city, beginService, beginServiceDepot, indexSalesman)) {
                        // 2.2.3.1 计算编号city的城市配送的紧急性(Uij)
                        deliveryUrgency = reqList.get(city + 1).getEndWindow() - (a.beginService[current_city] + reqList.get(current_city).getServiceTime() + distance);
                        // 2.2.3.2 城市current_city的开始服务时间，到城市city的开始服务时间。（这之间的服务时间和路程时间）Tij
                        timeDiference = beginService - a.beginService[current_city] - reqList.get(current_city).getServiceTime();
                        // 2.2.3.3 计算当前城市current_city与下一个访问城市city的紧密程度help，越大越好
                        // 最终的help相当于(v, s)中概率之内的那个公式（上半个公式）
                        help = 1.0 / (weight1 * distance + weight2 * timeDiference + weight3 * deliveryUrgency); // （相当于计算mij的公式）
                        help = Math.pow(help, beta);
                        help = help * Math.pow(pheromone[current_city][city + 1], alpha);
                        // 2.2.3.4 如果当前的插入方式比之前更优秀，则更新三个重要变量
                        if (help > value_best) {
                            next_city = city;
                            value_best = help;
                            salesman = indexSalesman;
                            bestBeginService = beginService;
                        }
                    }
                }
            }
        }

        // 3. 如果在已有路径中没有找到可行的（路径-城市），执行[insertion heuristic]，或添加路径。直至找出一个[城市和路径]的匹配
        // it means that not all the cities are covered and some customers has not yet been serviced
        // by using an insertion heuristic try to insert in the infeasible solution the customers not visited yet
        // when no more customer with feasible insertions can be found, start a new route/tour and add
        // one more vehicle for constructing a feasible solution
        if (next_city == VRPTW.n) {

            // 3.1 如果未分配的城市请求数量不超过10个，可以使用插入启发式方法，将未访问城市插入到已有路径中
            if ((a.toVisit > 0) && (a.toVisit <= 10)) {
                // 3.1.1 determine nodes that are not visited yet in the current ant's solution
                ArrayList<Integer> unroutedList = unroutedCustomers(a, vrp);
                // 3.1.2 skip over committed (defined) nodes when performing insertion heuristic
                lastCommitedIndexes = new ArrayList<Integer>();
                for (int index = 0; index < Ants.best_so_far_ant.usedVehicles; index++) {
                    pos = Controller.getLastCommitedPos(index);
                    lastCommitedIndexes.add(pos);
                }
                // 3.1.3 使用插入启发式方法
                startIndexTour = 0;
                InsertionHeuristic.insertUnroutedCustomers(a, vrp, unroutedList, startIndexTour, lastCommitedIndexes);
            }

            // 3.2 如果插入启发式操作之后，还有未分配的请求城市，则应该新建路径。
            // if no more unrouted customers can be feasible inserted in the solution and there are still
            // remaining unrouted customers, add a new tour
            if (a.toVisit > 0) {
                a.usedVehicles++;
                indexTour = a.usedVehicles - 1;
                a.tours.add(indexTour, new ArrayList<Integer>());
                a.tours.get(indexTour).add(-1);
                a.tour_lengths.add(indexTour, 0.0);
                a.currentQuantity.add(indexTour, 0.0);
                a.currentTime.add(indexTour, 0.0);
                a.addedEmptyTour = true;
                values[0] = -1;
                values[1] = indexTour;
            }
        }

        // 4. 如果可以找到一个[城市和路径]的匹配
        else {
            a.tours.get(salesman).add(next_city);
            a.visited[next_city] = true;
            a.toVisit--;
            a.currentTime.set(salesman, bestBeginService);
            a.beginService[next_city + 1] = bestBeginService;
            double newQuantity = a.currentQuantity.get(salesman) + reqList.get(next_city + 1).getDemand();
            a.currentQuantity.set(salesman, newQuantity);

            values[0] = next_city;
            values[1] = salesman;
        }
        return values;
    }

    /* joint mechanism */
    static int[] neighbour_choose_and_move_to_next(Ant a, VRPTW vrp) {
        int i = 0, j, help, city, salesman = 0;
        int current_city = 0;
        double rnd, partial_sum = 0., sum_prob = 0.0;
        double prob_ptr[][];
        double help1;
        int[] values = new int[2]; // 要返回的结果
        int[] tempCities = new int[a.usedVehicles];
        double distance, distanceDepot, arrivalTime, arrivalTimeDepot, beginService, beginServiceDepot;
        double deliveryUrgency, timeDiference = 0;
        ArrayList<Request> reqList = vrp.getRequests();

        // 1.if rand(0, 1) < q_0
        // 获取0~1的随机数，如果满足q_0条件，则在当前城市的邻近候选城市集合中，选择匹配“路径-城市”
        if ((q_0 > 0.0) && (Utilities.random01() < q_0)) {
            /*
             * with a probability q_0 make the best possible choice
             * according to pheromone trails and heuristic information, this corresponds to exploitation
             * we first check whether q_0 > 0.0, to avoid the very common case
             * of q_0 = 0.0 to have to compute a random number, which is
             * expensive computationally
             */
            values = neighbour_choose_best_next(a, vrp);
            return values;
        }

        // 2.otherwise【如果随机数不满足q_0条件。得到一个可能性概率分布的随机变量S，作为评价“路径-城市”匹配的标准】
        // 2.1初始化概率矩阵[prob_ptr]，prob_ptr[i][j]表示i车辆服务j城市的概率的分子
        prob_ptr = new double[a.usedVehicles][nn_ants + 1];
        for (j = 0; j < a.usedVehicles; j++) {
            for (i = 0; i < nn_ants; i++) {
                prob_ptr[j][i] = Double.POSITIVE_INFINITY;
            }
        }
        for (j = 0; j < (a.usedVehicles - 1); j++) {
            prob_ptr[j][nn_ants] = 0; // 已经被访问的城市
        }
        // a.usedVehicles-1代表的路径是，新增的路径，里面只有仓库这一个城市点，回到自身的距离是正无穷 
        prob_ptr[a.usedVehicles - 1][nn_ants] = Double.POSITIVE_INFINITY;

        // 2.2遍历路径，遍历临近候选城市集合，计算[prob_ptr矩阵]
        for (int indexSalesman = 0; indexSalesman < a.usedVehicles; indexSalesman++) {
            // 2.2.1 current_city city of Ant a in route indexSalesman
            int lastPos = a.tours.get(indexSalesman).size() - 1;
            current_city = a.tours.get(indexSalesman).get(lastPos);
            current_city++;
            // 2.2.2 遍历候选城市
            for (i = 0; i < Ants.nn_ants; i++) {
                city = VRPTW.instance.nn_list[current_city][i]; // 按照距离从小到大，取出城市编号
                // current_city ---> city
                distance = VRPTW.instance.distance[current_city][city];
                arrivalTime = a.currentTime.get(indexSalesman) + reqList.get(current_city).getServiceTime() + distance;
                beginService = Math.max(arrivalTime, reqList.get(city).getStartWindow());
                // city ---> depot
                distanceDepot = VRPTW.instance.distance[city][0];
                arrivalTimeDepot = beginService + reqList.get(city).getServiceTime() + distanceDepot;
                beginServiceDepot = Math.max(arrivalTimeDepot, reqList.get(0).getStartWindow());

                // 1.如果：不是可访问的请求城市，或者已经访问过该城市，或者不满足三个可行性条件
                if (!(vrp.getIdAvailableRequests().contains(city - 1)) || (a.visited[city - 1]) || (!VRPTW_ACS.isFeasible(vrp, a, city - 1, beginService, beginServiceDepot, indexSalesman))) {
                    /* city already visited */
                    prob_ptr[indexSalesman][i] = 0.0;
                }
                // 2.如果同时满足：是可访问的请求城市，未访问过该城市，满足三个可行性条件
                else if ((VRPTW_ACS.isFeasible(vrp, a, city - 1, beginService, beginServiceDepot, indexSalesman)) && (vrp.getIdAvailableRequests().contains(city - 1)) && !(a.visited[city - 1])) {
                    deliveryUrgency = reqList.get(city).getEndWindow() - (a.beginService[current_city] + reqList.get(current_city).getServiceTime() + distance);
                    timeDiference = beginService - a.beginService[current_city] - reqList.get(current_city).getServiceTime();
                    help1 = 1.0 / (weight1 * distance + weight2 * timeDiference + weight3 * deliveryUrgency);
                    help1 = Math.pow(help1, beta);
                    help1 = help1 * Math.pow(pheromone[current_city][city], alpha);
                    prob_ptr[indexSalesman][i] = help1; // 分子
                    tempCities[indexSalesman] = current_city; // 每条路径中当前城市的数组
                    sum_prob += prob_ptr[indexSalesman][i]; // 累计得到分母
                }
            }
        }

        // 3.如果所有的[candidate list]邻近候选城市集合都已经被访问过了，则使用[choose_best_next]，在[candidate list]之外的城市集合中寻找下一个访问城市
        if (sum_prob <= 0.0) {
            /* All cities from the candidate  are tabu (are already visited) */
            values = choose_best_next(a, vrp);
            return values;
        }

        // 4.如果在邻近候选城市集合中可以找到至少一个合法城市，根据偏概率，选择一个匹配“路径-城市”，并返回
        /* at least one neighbor is eligible, choose one according to the selection probabilities */
        else {
            // 4.1 下面代码是使用轮盘赌找出一条路径salesman和城市编号i
            // 根据总概率中每条路径概率的大小，找到一个最大概率匹配城市的路径
            rnd = Utilities.random01();
            rnd *= sum_prob;
            boolean done = false, // 是否匹配好“路径-城市”
                    forcedEnd = false; // 是否遍历完了路径中的城市
            partial_sum = 0;
            for (int indexSalesman = 0; indexSalesman < a.usedVehicles && !done; indexSalesman++) {
                i = 0;
                // 4.1.1 计算[partial_sum]的值，累计路径概率。[partial_sum]计算轮盘赌的值
                partial_sum += prob_ptr[indexSalesman][i];
                /* This loop always stops because prob_ptr[nn_ants] == HUGE_VAL */
                while (partial_sum <= rnd) {
                    i++;
                    if (i < 0) {
                        System.out.println("Iter=" + InOut.iteration + " Test: indexSalesman= " + indexSalesman + " i= " + i);
                        partial_sum += Double.POSITIVE_INFINITY;
                        forcedEnd = true;
                        break;
                    }
                    if (i < prob_ptr[indexSalesman].length) {
                        //System.out.println("Test: indexSalesman= " + indexSalesman + " i= " + i);
                        partial_sum += prob_ptr[indexSalesman][i];
                        salesman = indexSalesman;
                    } else if (i >= prob_ptr[indexSalesman].length) {
                        break;
                    }
                    // add a big value to the partial_sum to be sure that the while loop ends
                    else if (indexSalesman == (a.usedVehicles - 1) && i >= prob_ptr[indexSalesman].length && partial_sum <= rnd) {
                        partial_sum += Double.POSITIVE_INFINITY;
                        forcedEnd = true;
                    }
                }

                // 4.1.2 如果计算得到的累计路径概率，[partial_sum]大于轮盘赌抽到的值，则抽出此路径
                if (partial_sum > rnd) {
                    done = true;
                    if (!forcedEnd) {
                        salesman = indexSalesman;
                    } else {
                        // choose randomly a salesman to whom add the city
                        salesman = (int) (Math.random() * a.usedVehicles);
                    }
                }
            }

            // 4.2 使用完轮盘赌，遍历完所有路径，所有城市。还未找到合适的路径。使用[neighbour_choose_best_next]
            /* This may very rarely happen because of rounding if rnd is close to 1. */
            if (i == nn_ants) {
                values = neighbour_choose_best_next(a, vrp);
                return values;
            }

            current_city = tempCities[salesman];

            // 4.3 i<0的时候，找到匹配最优路径salesman的最优城市节点manIndex，和最优匹配值maxValue
            // i<0 表示i为仓库的时候
            int maxIndex = 0;
            double maxValue = Double.MIN_VALUE;
            if (i < 0) {
                maxValue = prob_ptr[salesman][0];
                for (j = 1; j < nn_ants; j++) {
                    if (prob_ptr[salesman][j] > maxValue) {
                        maxValue = prob_ptr[salesman][j];
                        maxIndex = j;
                    }
                }
                i = maxIndex;
            }

            // 4.4 匹配路径salesman与城市help的操作
            help = VRPTW.instance.nn_list[current_city][i];
            distance = VRPTW.instance.distance[current_city][help];
            arrivalTime = a.currentTime.get(salesman) + reqList.get(current_city).getServiceTime() + distance;
            beginService = Math.max(arrivalTime, reqList.get(help).getStartWindow());
            a.tours.get(salesman).add(help - 1);
            a.visited[help - 1] = true;
            a.toVisit--;
            a.currentTime.set(salesman, beginService);
            a.beginService[help] = beginService;
            double newQuantity = a.currentQuantity.get(salesman) + reqList.get(help).getDemand();
            a.currentQuantity.set(salesman, newQuantity);
            values[0] = help - 1;
            values[1] = salesman;
            return values;
        }
    }

    /* 返回蚂蚁a中未处理的可访问城市集合。get the list with the unvisited customers */
    static ArrayList unroutedCustomers(Ant a, VRPTW vrp) {
        // 1. 创建存储未访问城市的链表
        ArrayList<Integer> l = new ArrayList<Integer>(a.toVisit);

        // 2. 当前可访问城市编号的链表
        ArrayList<Integer> idKnownRequests = vrp.getIdAvailableRequests();
        int count = 0;

        // 3. 如果当前可访问城市编号的链表中，有城市未被访问，则放入未访问集合中
        // collect nodes missing from the ant's solution; depot is considered to be visisted by default
        for (int city : idKnownRequests) {
            if (a.visited[city] == false) {
                l.add(city);
                count++;
                if (count == a.toVisit) {
                    break;
                }
            }
        }
        return l;
    }

    /**
     * 局部更新信息素 [local pheromone update rule]
     * removes some pheromone on edge just passed by the ant
     */
    static void local_acs_pheromone_update(Ant a, int indexSalesman) {
        int h, j;
        int lastPos = a.tours.get(indexSalesman).size() - 1;
        j = a.tours.get(indexSalesman).get(lastPos);
        h = a.tours.get(indexSalesman).get(lastPos - 1);
        j++;
        h++;

        /* still additional parameter has to be introduced */
        pheromone[h][j] = (1. - local_rho) * pheromone[h][j] + local_rho * trail_0;
        pheromone[j][h] = pheromone[h][j];
    }

    /* 使用蚂蚁a，更新全局信息素 */
    static void global_acs_pheromone_update(Ant a) {
        int i, j, h, k, size;
        double d_tau;
        d_tau = 1.0 / (double) a.total_tour_length;

        for (i = 0; i < a.usedVehicles; i++) {
            size = a.tours.get(i).size();
            for (k = 0; k < size - 1; k++) {
                j = a.tours.get(i).get(k);
                h = a.tours.get(i).get(k + 1);
                j++;
                h++;
                pheromone[j][h] = (1. - rho) * pheromone[j][h] + rho * d_tau;
                pheromone[h][j] = pheromone[j][h];
            }
        }
    }

    /* 计算蚂蚁a的，最长路径和最短路径的差值 */
    static double computeToursAmplitude(Ant a) {
        double min, max;
        int i;

        min = a.tour_lengths.get(0);
        max = a.tour_lengths.get(0);
        for (i = 1; i < a.tours.size(); i++) {
            if (a.tour_lengths.get(i) < min) {
                min = a.tour_lengths.get(i);
            }
            if (a.tour_lengths.get(i) > max) {
                max = a.tour_lengths.get(i);
            }
        }

        return (max - min);
    }

    /**
     * find the best ant of the current iteration（返回本次蚁群迭代的最优蚂蚁的编号）
     * (the one with the lowest number of used vehicles and with smaller total traveled distance)
     *
     * @return
     */
    static int find_best() {
        double min1, min2;
        int k1, k2, k2_min;

        //1. 先根据车辆数量优先级比较
        // first detect the ant which uses the minimum number of vehicles
        min1 = ants[0].usedVehicles;
        for (k1 = 1; k1 < n_ants; k1++) {
            if (ants[k1].usedVehicles < min1) {
                min1 = ants[k1].usedVehicles;
            }
        }

        // 2. 再根据总路程进行比较
        // among the vehicles which use the minimum number of vehicles, select the best ant as the one with the minimum total distance for its traveled tours
        min2 = Double.MAX_VALUE;
        k2_min = 0;
        for (k2 = 0; k2 < n_ants; k2++) {
            if (ants[k2].usedVehicles == min1) {
                if (ants[k2].total_tour_length < min2) {
                    min2 = ants[k2].total_tour_length;
                    k2_min = k2;
                }
            }
        }
        return k2_min;
    }

    /**
     * 尝试将未处理城市请求加入到指定的路径末尾
     * 这个方法一般是用于，刚生成一条新的路径，使用新路径处理城市请求
     */
    static void choose_closest_nn(Ant a, int indexSalesman, VRPTW vrp) {
        int current_city, next_city, indexTour;
        double distance, distanceDepot, arrivalTime, arrivalTimeDepot, beginService, beginServiceDepot;
        double timeDiference, deliveryUrgency, bestBeginService = 0, minValue, metricValue;
        ArrayList<Request> reqList = vrp.getRequests(); // 请求城市的集合
        ArrayList<Integer> idKnownRequests = vrp.getIdAvailableRequests(); // 请求中的城市编号集合

        while (a.toVisit > 0) {
            next_city = VRPTW.n;
            minValue = Integer.MAX_VALUE;

            // 1.路径indexSalesman的末端城市的编号
            int lastPos = a.tours.get(indexSalesman).size() - 1;
            current_city = a.tours.get(indexSalesman).get(lastPos);
            current_city++;

            // 2.找到合适的请求城市：next_city
            for (int city : idKnownRequests) {
                if (a.visited[city])
                    ;  //city already visited
                else {
                    distance = VRPTW.instance.distance[current_city][city + 1];
                    arrivalTime = a.currentTime.get(indexSalesman) + reqList.get(current_city).getServiceTime() + distance;
                    beginService = Math.max(arrivalTime, reqList.get(city + 1).getStartWindow());

                    distanceDepot = VRPTW.instance.distance[city + 1][0];
                    arrivalTimeDepot = beginService + reqList.get(city + 1).getServiceTime() + distanceDepot;
                    beginServiceDepot = Math.max(arrivalTimeDepot, reqList.get(0).getStartWindow());

                    if (VRPTW_ACS.isFeasible(vrp, a, city, beginService, beginServiceDepot, indexSalesman)) {
                        // compute the value of the "closeness" metric; this metric tries to account
                        // for both geographical and temporal closeness of customers
                        timeDiference = beginService - a.beginService[current_city] - reqList.get(current_city).getServiceTime();
                        deliveryUrgency = reqList.get(city + 1).getEndWindow() - (a.beginService[current_city] + reqList.get(current_city).getServiceTime() + distance);
                        metricValue = weight1 * distance + weight2 * timeDiference + weight3 * deliveryUrgency;
                        if (metricValue < minValue) {
                            next_city = city;
                            minValue = metricValue;
                            bestBeginService = beginService;
                        }
                    }
                }
            }

            // 3.如果可以找到next_city放入到路径中，则插入路径中；否则跳出此程序
            if (next_city == VRPTW.n) { // no more nodes can be feasible added in the tour
                break;
            } else {
                a.tours.get(indexSalesman).add(next_city);
                a.visited[next_city] = true;
                a.toVisit--;
                a.currentTime.set(indexSalesman, bestBeginService);
                a.beginService[next_city + 1] = bestBeginService;
                a.currentQuantity.set(indexSalesman, a.currentQuantity.get(indexSalesman) + reqList.get(next_city + 1).getDemand());
            }
        }
    }
}